﻿public class Solution {
    public int[] NextGreaterElement(int[] nums1, int[] nums2) 
    {
        // 结果数组
        int[] result = new int[nums1.Length];
        Array.Fill(result, -1);
        
        // 映射字典
        Dictionary<int, int> nums1Dic = new Dictionary<int, int>();
        for (int i = 0; i < nums1.Length; i++)
        {
            nums1Dic[nums1[i]] = i;
        }
        
        // 单调栈问题
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < nums2.Length; i++)
        {
            while (stack.Count > 0)
            {
                int top = stack.Peek();
                if (top < nums2[i])
                {
                    stack.Pop();

                    if (nums1Dic.ContainsKey(top))
                    {
                        result[nums1Dic[top]] = nums2[i];
                    }
                }
                else break;
            }
            stack.Push(nums2[i]);
        }
        return result;
    }

    public static void Main(string[] args)
    {
        int[] nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2];
        Solution solution = new Solution();
        int[] result = solution.NextGreaterElement(nums1, nums2);

        foreach (int res in result)
        {
            Console.Write($"{res} ");
        }
        Console.WriteLine();
    }
}